In a typical data processing environment, data may be transmitted in multiple packets, e.g., words, from one element, e.g., cache, to another element, e.g., processor, over a bus, e.g., parallel bus. A hamming distance may refer to the number of non-matching bits, i.e., the number of bits that changed state, in two consecutively transmitted data packets. For example, a first 16-bit data word may be sent from a cache to a processor comprising of all 1's followed by a second data word of all 0's. In the above example, the hamming distance would be 16 representing that each bit in the consecutively transmitted data packets changed state. The hamming distance may be represented by a particular voltage which may then be compared to a threshold voltage level. If the hamming distance is above or below the threshold voltage, an activity may occur. Hamming distance comparison may be used in many applications including image processing and bus inversion.
Bus inversion may refer to transmitting the complement value of the data bits instead of the true value of the data bits when the number of bits to be switched is greater than half of the number of bits in the transmitted packet, e.g., word. Each time a bit changes state, a bus driver associated with that bit may be asserted to switch the state of the bit. Switching, however, consumes a significant amount of power. Consequently, it would be desirable to minimize switching activity. Bus inversion may be one method of minimizing at least in part switching activity. Bus inversion may minimize at least in part switching activity by transmitting the complement value of the data bits instead of the true value of the data bits when the number of bits to be switched is greater than half of the number of bits in the transmitted packet, e.g., word.
For example, a first data word may be sent from a cache to a processor with the binary value of 1111111111111111 followed by a second data word with the binary value of 0000000001111111. As illustrated, more than half of the bits in the second data word have changed in value with respect to the first data word. Instead of transmitting the true value of 0000000001111111 thereby switching nine bits, the value of 1111111110000000 may be transmitted thereby only switching seven bits. In conjunction with transmitting the complemented values, an extra bit commonly referred to as the inversion bit may be transmitted which indicates whether or not to invert the values of the transmitted data values
One method of performing hamming distance comparison to perform bus inversion uses a hamming distance comparator as illustrated in FIG. 1. The hamming distance comparator of FIG. 1 may implement a Capacitor Threshold Logic (CTL) gate as discussed further below. CTL may refer to a dynamic circuit which requires a periodic refresh or precharge cycle, but unlike conventional dynamic Complementary Metal Oxide Semiconductor (CMOS) gates, the circuit may be operated in synchronous as well as in asynchronous mode.
Referring to FIG. 1, a hamming distance comparator 100 may be used to determine whether to invert the bus or not, i.e., implement bus inversion. Hamming distance comparator 100 may comprise a bus 101 coupled between one element, e.g., cache, and another element, e.g., processor, in a data processing system. Hamming distance comparator 100 may further comprise a plurality of latches 102A-D that may be used to maintain one of two states of a particular bit in a transmitted data packet. Latches 102A-D may collectively or individually be referred to as latches 102 or latch 102. For example, if the bits 1011 were transmitted on bus 101, then latch 102A may maintain the state, e.g., binary value of 1, for the least significant bit. Latch 102B may maintain the state, e.g., binary value of 1, for the bit adjacent to the least significant bit. Latch 102C may maintain the state, e.g., binary value of 0, for the bit second from the least significant bit. Latch 102D may maintain the state, e.g., binary value of 1, for the most significant bit. Exclusive-OR (XOR) gates 103A-D may each be connected to an input and an output of a corresponding latch 102A-D, respectively, in order to capture the present value and the past value of a particular bit. XOR gates 103A-D may collectively or individually be referred to as XOR gates 103 or XOR gate 103, respectively. By capturing the present and past value of a particular bit, XOR gate 103 may determine whether the value for that bit position changed in value from a first data transfer to a second data transfer. XOR gate 103 may logically output a “1” when the inputs to XOR gate 103 differ in state. Hence, when the value for a bit position changes, e.g., 0 to binary value of 1, then the corresponding XOR gate 103 may output a “1.” When the value for a bit position does not change state, then the corresponding XOR gate 103 may output a “0.”
Hamming distance comparator 100 may further comprise a CTL gate 110. CTL gate 110 may comprise CTL switches 104A-D coupled to XOR gates 103A-D, respectively. CTL switches 104A-D may collectively or individually be referred to as CTL switches 104 or CTL switch 104, respectively. CTL gate 110 may further comprise capacitors 105A-D coupled to CTL switches 104A-D, respectively. Capacitors 105A-D may collectively or individually be referred to as capacitors 105 or CTL capacitor 105, respectively. CTL gate 110 may further comprise a CTL comparator 107 coupled to each CTL capacitor 105A-D via a common line 106. CTL comparator 107 may be configured to change the state of the inversion bit used to indicate whether or not to transmit the complemented bit values in the received data packet based on the voltage level of common line 106. If the voltage level of common line 106 exceeds a threshold voltage established by CTL comparator 107, then CTL comparator 107 may be configured to change the state of the inversion bit to indicate to transmit the complemented bit values in the received data packet. If the voltage level of common line 106 falls below the threshold voltage established by CTL comparator 107, then CTL comparator 107 may be configured to not change the state of the inversion bit to indicate to transmit the true bit values in the received data packet. CTL gate 110 may further comprise a threshold column 108 coupled to common line 106. Threshold column 108 may be configured to adjust or shift the threshold voltage level, e.g., decrease threshold voltage level, established by CTL comparator 107 during a reset state. The amount of the adjustment or shift of the threshold voltage level may determine the number of CTL capacitors 105 that have to be charged up in order to activate CTL comparator 107 as described below.
Hamming distance comparator 100 may operate in two states commonly referred to as a reset state and an evaluation state. During the reset state, each CTL capacitor 105 may be discharged while a value of a bit on bus 101 is latched by the appropriate latch 102. During the evaluation state, CTL switch 104 may be configured to pass the value outputted by the associated XOR gate 103 to the associated CTL capacitor 105. As stated above, XOR gate 103 may logically output a “1” when the inputs to XOR gate 103 differ in state. Hence, when the value for a bit position changes, e.g., 0 to binary value of 1, then the corresponding XOR gate 103 may output a “1.” When the value for a bit position does not change state, then the corresponding XOR gate 103 may output a “0.” Upon CTL switch 104 passing the value outputted by the associated XOR gate 103 to the associated CTL capacitor 105, CTL capacitor 105 may charge up if the corresponding XOR gate 103 outputted a “1.” When CTL capacitor 105 charges up, the voltage of common line 106 increases. If XOR gate 103 outputs a “0”, then the associated CTL switch 104 passes a “0” to the associated CTL capacitor 105 thereby remaining discharged and not increasing the voltage of common line 106.
If the voltage level of common line 106 increases to above a predetermined threshold level, then CTL comparator 107 may change the state of the inversion bit to indicate to transmit the complemented bit values in the received data packet. In other words, if the number of bits that changed state in two consecutively transmitted data packets, i.e., the hamming distance, is greater than a certain number, then CTL comparator 107 may change the state of the inversion bit to indicate to transmit the complemented bit values in the received data packet. If the voltage level of common line 106 did not increase to above a predetermined threshold level, then CTL comparator 107 may not change the state of the inversion bit and hence indicate to send the true values in the received data packet. In other words, if the number of bits that changed state in two consecutively transmitted data packets, i.e., the hamming distance, is not greater than a certain number, then CTL comparator 107 may not change the state of the inversion bit and hence indicate to send the true values in the received data packet.
While the above hamming distance comparator implements hamming distance comparison to perform bus inversion, the hamming distance comparator comprises several levels of logic including latches and XOR gates. By having several levels of logic including latches and XOR gates, the complexity of the hamming distance comparator increases which increases costs and decreases performance.
It would therefore be desirable to perform hamming distance comparison without implementing explicit latches or Exclusive Or (XOR) gates using capacitive threshold logic.